忍者算法

Appearance

从食堂打饭到链表合并：巧解K路归并问题 ​

生活中的多路合并 ​

想象你是一个大学食堂的管理员。食堂有k个打饭窗口，每个窗口前都排着一队按身高从矮到高的学生（就像我们的有序链表）。你的任务是将所有学生重新排成一个队，依然要保持按身高从矮到高的顺序。这就是我们今天要讨论的合并k个升序链表问题的生动写照。

问题的本质与挑战 ​

LeetCode第23题"合并K个升序链表"要求我们将K个有序链表合并成一个新的有序链表。这个问题乍看简单，实则暗藏玄机：如何在保证结果有序的同时，又能达到最优的时间复杂度？

例如：

输入：
[
  1→4→5,
  1→3→4,
  2→6
]
输出：1→1→2→3→4→4→5→6

解题思路的进化 ​

方法一：逐个合并法 ​

就像食堂管理员最直观的想法：先合并前两队，再把结果和第三队合并，以此类推。这种方法简单但效率不高，因为前面的元素会被重复比较多次。

方法二：分治合并法 ​

更聪明的方式是采用分治思想：先把k个队伍分成两半，各自合并后再合并到一起。就像举办体育比赛的淘汰赛制一样，这样可以显著减少比较次数。

方法三：优先队列法 ​

最优雅的解法是利用优先队列：每个打饭窗口派出当前队伍的第一个学生到一个中心区域（优先队列），始终从中选出最矮的学生，然后该学生所在的窗口再派出下一个学生。这样我们可以始终保证选出的是当前最小的元素。

详细代码实现 ​

让我们先来看最优雅的优先队列解法：

java
public ListNode mergeKLists(ListNode[] lists) {
    // 特判：处理空数组或全是空链表的情况
    if (lists == null || lists.length == 0) return null;
    
    // 创建优先队列，按节点值升序排列
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
    
    // 将所有链表的头节点加入优先队列
    for (ListNode node : lists) {
        if (node != null) {
            pq.offer(node);
        }
    }
    
    // 创建虚拟头节点
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    
    // 不断从优先队列中取出最小节点
    while (!pq.isEmpty()) {
        // 取出并移除优先队列中的最小节点
        ListNode curr = pq.poll();
        tail.next = curr;
        tail = tail.next;
        
        // 如果当前节点还有后续节点，加入优先队列
        if (curr.next != null) {
            pq.offer(curr.next);
        }
    }
    
    return dummy.next;
}

再来看分治合并法的实现：

java
public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    return mergeSort(lists, 0, lists.length - 1);
}

private ListNode mergeSort(ListNode[] lists, int left, int right) {
    // 只剩一个链表时直接返回
    if (left == right) return lists[left];
    
    // 分治处理
    int mid = left + (right - left) / 2;
    ListNode leftList = mergeSort(lists, left, mid);
    ListNode rightList = mergeSort(lists, mid + 1, right);
    
    // 合并两个有序链表
    return mergeTwoLists(leftList, rightList);
}

private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    
    tail.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

复杂度分析与比较 ​

优先队列法：

  • 时间复杂度：O(N logK)，N是所有节点总数，K是链表个数
  • 空间复杂度：O(K)，优先队列中最多K个节点
  • 优点：实现优雅，处理过程清晰
  • 缺点：需要额外的数据结构

分治合并法：

  • 时间复杂度：O(N logK)
  • 空间复杂度：O(logK)，递归调用栈的深度
  • 优点：不需要额外的数据结构
  • 缺点：实现稍复杂，递归调用有开销

逐个合并法：

  • 时间复杂度：O(NK)
  • 空间复杂度：O(1)
  • 优点：实现最简单
  • 缺点：效率较低，重复比较次数多

实战技巧总结 ​

  1. 优先队列的初始化技巧：把Lambda表达式用于比较器定义使代码更简洁
  2. 虚拟头节点的使用：简化边界情况的处理
  3. 分治时计算中点：使用 left + (right - left) / 2 避免整数溢出
  4. 合并过程的细节：注意指针更新的顺序，防止断链

应用场景延伸 ​

K路归并的思想在实际开发中非常常见：

  • 多路文件合并
  • 数据库的多路归并
  • 分布式系统的结果聚合
  • 实时数据流的合并排序

小结 ​

合并K个升序链表的问题教会我们：

  1. 如何将简单问题（合并两个有序链表）扩展到复杂场景
  2. 不同解法之间的权衡取舍
  3. 数据结构（优先队列）在算法优化中的重要作用
  4. 分治思想的实际应用

记住：解决复杂问题如同管理食堂打饭，找到合适的策略才能实现最优效率！

补充思考：

  • 如果链表数量K很大，如何优化内存使用？
  • 如果是流式数据，如何调整算法？
  • 如何处理链表长度相差很大的情况？

作者：忍者算法 公众号：忍者算法

我准备了一份刷题清单，以及这些题目的详细题解，覆盖了绝大部分常见面试题。我可以很负责任地说，只要你把这些题真正掌握了，80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～